package leetcode.editor.cn;
//给定单个链表的头
// head ，使用 插入排序 对链表进行排序，并返回 排序后链表的头 。 
//
// 插入排序 算法的步骤: 
//
// 
// 插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。 
// 每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。 
// 重复直到所有输入数据插入完为止。 
// 
//
// 下面是插入排序算法的一个图形示例。部分排序的列表(黑色)最初只包含列表中的第一个元素。每次迭代时，从输入数据中删除一个元素(红色)，并就地插入已排序的列表
//中。 
//
// 对链表进行插入排序。 
//
// 
//
// 
//
// 示例 1： 
//
// 
//
// 
//输入: head = [4,2,1,3]
//输出: [1,2,3,4] 
//
// 示例 2： 
//
// 
//
// 
//输入: head = [-1,5,3,4,0]
//输出: [-1,0,3,4,5] 
//
// 
//
// 提示： 
//
// 
// 
//
// 
// 列表中的节点数在 [1, 5000]范围内 
// -5000 <= Node.val <= 5000 
// 
//
// Related Topics 链表 排序 👍 651 👎 0


//leetcode submit region begin(Prohibit modification and deletion)

import java.util.ArrayList;
import java.util.List;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution267 {


    public ListNode insertionSortList(ListNode head) {
        // 1. 首先判断给定的链表是否为空，若为空，则不需要进行排序，直接返回。
        if (head == null) {
            return head;
        }

        // 2. 链表初始化操作
        ListNode dummyHead = new ListNode(0); // 引入哑节点
        dummyHead.next = head;                // 目的是在head之前插入节点
        ListNode lastSorted = head;           // 维护lastSorted为链表已经排好序的最后一个节点并初始化
        ListNode curr = head.next;            // 维护curr 为待插入的元素并初始化

        // 3. 插入排序
        while (curr != null) {
            if (lastSorted.val <= curr.val) {     // 说明curr应该位于lastSorted之后
                lastSorted = lastSorted.next;   // 将lastSorted后移一位,curr变成新的lastSorted
            } else {                              // 否则,从链表头结点开始向后遍历链表中的节点
                ListNode prev = dummyHead;      // 从链表头开始遍历 prev是插入节点curr位置的前一个节点
                while (prev.next.val <= curr.val) { // 循环退出的条件是找到curr应该插入的位置
                    prev = prev.next;
                }
                // 以下三行是为了完成对curr的插入（配合题解动图可以直观看出）
                lastSorted.next = curr.next;
                curr.next = prev.next;
                prev.next = curr;
            }
            curr = lastSorted.next; // 此时 curr 为下一个待插入的元素
        }
        // 返回排好序的链表
        return dummyHead.next;
    }


    public ListNode insertionSortList2(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode p = head;
        while (p != null && p.next != null) {
            ListNode q = p.next;
            ListNode t = head;
            while (t != q) {
                if (t.val >= q.val) {
                    swap2(t, q);
                    break;
                }
                t = t.next;
            }
            p = p.next;
        }
        return head;
    }

    /**
     * 将
     *
     * @param a
     * @param b
     */
    private void swap2(ListNode a, ListNode b) {
        int temp = b.val;
        ListNode p = a;
        int value = p.val;
        while (p != b) {
            int next = p.next.val;
            p.next.val = value;
            value = next;
            p = p.next;
        }

        a.val = temp;
    }


    public ListNode insertionSortList1(ListNode head) {
        if (head == null) {
            return null;
        }
        //存到 list 中去
        List<ListNode> list = new ArrayList<>();
        while (head != null) {
            list.add(head);
            head = head.next;
        }
        sort(list);
        return list.get(0);
    }

    private void sort(List<ListNode> list) {
        for (int i = 0; i < list.size() - 1; i++) {
            int insertIndex = i + 1;
            while (insertIndex > 0) {
                if (list.get(insertIndex).val < list.get(insertIndex - 1).val) {
                    swap1(list, insertIndex, insertIndex - 1);
                    insertIndex--;
                } else {
                    break;
                }
            }
        }
    }

    private void swap1(List<ListNode> list, int i, int j) {
        int temp = list.get(i).val;
        list.get(i).val = list.get(j).val;
        list.get(j).val = temp;
    }

    public static void main(String[] args) {
        ListNode a = new ListNode(1);
        ListNode b = new ListNode(3, a);
        ListNode c = new ListNode(2, b);
        ListNode d = new ListNode(4, c);

        Solution267 s = new Solution267();
        s.insertionSortList(d);
    }

    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
}
//leetcode submit region end(Prohibit modification and deletion)
